문서의 임의 삭제는 제재 대상으로, 문서를 삭제하려면 삭제 토론을 진행해야 합니다. 문서 보기문서 삭제토론 동적 계획법 (문단 편집) == 구현 == 동적 계획법의 접근 방식은 기본적으로 [[분할 정복 알고리즘]]과 비슷하다. 위에서도 설명했지만 동적 계획법을 사용하는 알고리즘 역시 주어진 문제를 부분 문제로 나누어 각 부분 문제의 답을 계산하고, 이 계산한 결과값을 이용해 원래 문제의 답을 산출하기 때문이다. 여기서 분할정복과 차이가 생기는 부분은 원래의 문제를 부분 문제로 나누는 방식에 있다. 동적 계획법의 경우 주어진 문제를 나눌 때 부분 문제를 최대한 많이 이용하도록 나눈 다음, 주어진 부분 문제의 정답을 한 번만 계산하고 저장해둔 뒤 다시 한 번 이 부분 문제를 이용할 때에는 저장해둔 정답을 바로 산출하여 이용함으로써 속도를 향상시킨다. [[파일:5-23-2.png|width=500]] 즉, 동적 계획법은 그림과 같이 [[그리디 알고리즘#s-2.1|최적 부분 구조(Optimal Substructure)]]를 지닌 중복된 하위 문제들(Overlapping Subproblems)을 분할 정복으로 풀이하는 문제해결 패러다임이다.저장 버튼을 클릭하면 당신이 기여한 내용을 CC-BY-NC-SA 2.0 KR으로 배포하고,기여한 문서에 대한 하이퍼링크나 URL을 이용하여 저작자 표시를 하는 것으로 충분하다는 데 동의하는 것입니다.이 동의는 철회할 수 없습니다.캡챠저장미리보기